/**
 * @Author Fizz Pu
 * @Date 2020/9/1 下午4:19
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
import UnionSearchSet.UnionSearchSet;
import java.util.Arrays;
import java.util.HashSet;

/**
 * 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，
 * B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
 * <p>
 * 给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，
 * 表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/friend-circles
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Lee547 {
    public static void main(String[] args) {
        UnionSearchSet unionSearchSet = new UnionSearchSet(3);
        System.out.println(unionSearchSet);
        unionSearchSet.union(0, 1);
        unionSearchSet.union(1, 2);
        System.out.println(unionSearchSet.countSetNumber());
        int[][] M = new int[][]{
                {1, 1, 0}, {1, 1, 1}, {0, 1, 1}
        };
        System.out.println(findCircleNum(M));
    }

    public static int findCircleNum(int[][] M) {
        int N = M.length;
        UnionSearchSet unionSearchSet = new UnionSearchSet(N);
        for (int row = 0; row < N; ++row) {
            for (int column = row + 1; column < N; ++column) { // 不需要从0开始判断
                if (M[row][column] == 1) unionSearchSet.union(column, row);
            }
        }
        return unionSearchSet.countSetNumber();
    }
}
